import jdk.nashorn.internal.runtime.regexp.joni.ast.StringNode;

/**
 * Created by L.jp
 * Description:给定一个m x n 二维字符网board 和一个字符串单词word 。如果word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 * User: 86189
 * Date: 2022-12-05
 * Time: 23:32
 */
public class Solution {
    public boolean exist(char[][] board, String word) {
        char[] words=word.toCharArray();
        int k=0;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j <board[0].length; j++){
                if(dfs(board,words,i,j,0)) return true;
            }
        }
        return false;
    }
    //搜索周围四个方向,index是遍历当前字符数组的下标
    private boolean dfs (char[][] board , char[] words , int i , int j , int index) {
        //递归结束,越界或者矩阵当前字符不等于字符数组当前的字符，返回false
        if(i<0 || j<0 || i>= board.length || j>=board[0].length || board[i][j]!=words[index]) return false;
        //如果遍历到了字符数组结尾，那么就返回真
        if(index==words.length-1) return true;
        //当前节点标记为遍历过
        board[i][j]='*';
        //深搜
        boolean isContain=dfs( board,words,i-1,j,index+1 ) || dfs( board,words,i,j+1,index+1 )
                         || dfs( board,words,i+1,j,index+1 ) || dfs( board,words,i,j-1,index+1 );
        //回溯,回归上一个位置原来的字符，就是index与[i,j]相等的字符
        board[i][j]=words[index];
        return isContain;
    }
    
}
